In asynchronous transfer mode packet protocols and other packet switched systems, a current procedure for restoration of packets lost in transmission is by means of automatic retransmission requests. In a system where transmission latency through the network is a few packets or 10's of packets, the size of transmission buffers required to be maintained at transmitting nodes and receiving nodes is small for automatic transmission request protocol exchanges. However, in transmission systems where path delays are large, i.e., where the path includes satellite links or long distance optical fiber links carrying high data rates, accommodation of an automatic retransmission request protocol may incur very large data buffers. Further, in data networks where communications occur over a large variety of links, each node must retain a buffering capacity that is related to the longest delay path (in numbers of packets in transition over the network).
Packet losses in a packet network may result from buffer overflows, switch contentions or from interference and noise encountered in typical links that comprise the network. The major share of packet losses result from buffer overflows and from switch blockages and contention. The probability of packet loss is statistically determined by the percentage of the maximum network capacity that the actual traffic represents. In certain systems, packet loss probabilities and network delay queue lengths become intolerably large when the traffic approaches a range of approximately 35% of maximum network capacity.
New networks, termed "fast packet networks", use asynchronous optical network media, have enormous capacity and very high noise immunity over their individual links. In such networks most packet losses come from electronic switching and buffers, rather than from optical transmission portions of the network. Such networks span the continental United States and interconnect continents via transoceanic cables. In those networks, delays due to propagation are long and nodal buffers needed to store packets for possible retransmission can become very large for a busy traffic nodes in the network. This places great importance on the ability of the networks' packet recovery system to dispense with almost all re-transmission requests since most node buffer assets to support re-transmission are otherwise occupied.
To reduce retransmission requests over the network, prior art systems have used various parity systems to enable recovery of individual data segment losses or entire packet losses at a destination node. Various of such systems can be found in the following U.S. Pat. Nos. 4,888,767 to Furuya et al.; 4,507,782 to Kunimasa et al.; 4,447,902 to Wilkinson; 4,599,722 to Mortimer; and 4,769,818 to Mortimer. Error recovery in packet systems used for video information is also considered in "Packet Video and Its Integration Into the Network Architecture" Karlsson et al, IEEE Journal on Selected Areas in Communications, Vol. 7, No. 5, June, 1989, pp. 739-751.
An effective recovery system that enables recovery of data fields from a series of packets is described by Shacham et al. in "Packet Recovery in High Speed Networks Using Coding and Buffer Management", INFOCOM PROCEEDINGS, 1990, pp. 124-131. Shacham et al. divides groups of data packets into blocks of packets of a predetermined size ("L") and adds to each block a number of parity packets that contain error-control bits. The number of parity packets determines the maximum number of lost data packets that can be recovered. Shacham et al. compute a parity packet as follows: the first bit of a parity packet is the modulo 2 sum (exclusive or) of the first bit of the data field of all L packets comprising a block; the second bit of the parity packet is the modulo 2 sum of the second bit of the data field of the L packets and so on. The parity packet is transmitted as the (L+1.sup.th) packet after transmission of the L data packets.
At a destination node, the received L packets are stored in a buffer, together with the L+1.sup.th parity packet. If one packet is determined to be missing or is received in error (e.g. a succession number is incorrect or a CRC check indicates a failure), the receiving node computes a modulo-2 sum for each bit in data fields in properly received packets and includes the parity packet in that computation. The result is a reconstruction of the data field of the errant packet.
The use of additional parity packet(s) for a block of packets places an increased load on the network and further leads to possible additional network congestion. However, the parity packet procedure does enable effective recovery of lost data packets and in many system applications, it will reduce last packet probability to an acceptably low value.
Accordingly, it is an object of this invention to provide an improved packet recovery system that is adaptive to network congestion conditions.
It is another object of this invention to provide an improved packet recovery system that employs parity packets to enable packet recovery, wherein a block of packets of size L, for which a parity may be varied in size in accordance with network conditions.
It is yet another object of this invention to provide a packet recovery system that is adaptive in accordance with a determined buffer fill status indication, bit error rate indications, and/or packet transmission latency parameters.